Smallest string with swaps [Union Find]

Time: O(NLogN); Space: O(N); medium

You are given a string s, and an array of pairs of indices in the string pairs where pairs[i] = [a, b] indicates 2 indices(0-indexed) of the string.

You can swap the characters at any pair of indices in the given pairs any number of times.

Return the lexicographically smallest string that s can be changed to after using the swaps.

Example 1:

Input: s = “dcab”, pairs = [[0,3],[1,2]]

Output: “bacd”

Explanation:

• Swap s[0] and s[3], s = “bcad”

• Swap s[1] and s[2], s = “bacd”

Example 2:

Input: s = “dcab”, pairs = [[0,3],[1,2],[0,2]]

Output: “abcd”

Explanation:

• Swap s[0] and s[3], s = “bcad”

• Swap s[0] and s[2], s = “acbd”

• Swap s[1] and s[2], s = “abcd”

Example 3:

Input: s = “cba”, pairs = [[0,1],[1,2]]

Output: “abc”

Explanation:

• Swap s[0] and s[1], s = “bca”

• Swap s[1] and s[2], s = “bac”

• Swap s[0] and s[1], s = “abc”

Constraints:

• 1 <= len(s) <= 10^5

• 0 <= len(pairs) <= 10^5

• 0 <= pairs[i][0], pairs[i][1] < s.length

• s only contains lower case English letters.

Hints:

1. Think of it as a graph problem.

2. Consider the pairs as connected nodes in the graph, what can you do with a connected component of indices?

3. We can sort each connected component alone to get the lexicographically minimum string.

1. Union Find

import collections

class UnionFind(object):
    def __init__(self, n):
        self.set = [x for x in range(n)]

    def find_set(self, x):
        if self.set[x] != x:
            self.set[x] = self.find_set(self.set[x])  # path compression.
        return self.set[x]

    def union_set(self, x, y):
        x_root, y_root = map(self.find_set, (x, y))
        if x_root == y_root:
            return False
        self.set[max(x_root, y_root)] = min(x_root, y_root)
        return True

class Solution1(object):
    """
    Time: O(NLogN)
    Space: O(N)
    """
    def smallestStringWithSwaps(self, s, pairs):
        """
        :type s: str
        :type pairs: List[List[int]]
        :rtype: str
        """
        union_find = UnionFind(len(s))

        for x,y in pairs:
            union_find.union_set(x, y)
        components = collections.defaultdict(list)

        for i in range(len(s)):
            components[union_find.find_set(i)].append(s[i])

        for i in components.keys():
            components[i].sort(reverse=True)

        result = []
        for i in range(len(s)):
            result.append(components[union_find.find_set(i)].pop())

        return ''.join(result)

sol = Solution1()

s = "dcab"
pairs = [[0,3],[1,2]]
assert sol.smallestStringWithSwaps(s, pairs) == "bacd"

s = "dcab"
pairs = [[0,3],[1,2],[0,2]]
assert sol.smallestStringWithSwaps(s, pairs) == "abcd"

s = "cba"
pairs = [[0,1],[1,2]]
assert sol.smallestStringWithSwaps(s, pairs) == "abc"

2. DFS

import collections

class Solution2(object):
    def smallestStringWithSwaps(self, s, pairs):
        """
        :type s: str
        :type pairs: List[List[int]]
        :rtype: str
        """
        def dfs(i, adj, lookup, component):
            lookup.add(i)
            component.append(i)
            for j in adj[i]:
                if j in lookup:
                    continue
                dfs(j, adj, lookup, component)

        adj = collections.defaultdict(list)
        for i, j in pairs:
            adj[i].append(j)
            adj[j].append(i)
        lookup = set()
        result = list(s)
        for i in range(len(s)):
            if i in lookup:
                continue
            component = []
            dfs(i, adj, lookup, component)
            component.sort()
            chars = sorted(result[k] for k in component)
            for comp, char in zip(component, chars):
                result[comp] = char
        return ''.join(result)

sol = Solution1()

s = "dcab"
pairs = [[0,3],[1,2]]
assert sol.smallestStringWithSwaps(s, pairs) == "bacd"

s = "dcab"
pairs = [[0,3],[1,2],[0,2]]
assert sol.smallestStringWithSwaps(s, pairs) == "abcd"

s = "cba"
pairs = [[0,1],[1,2]]
assert sol.smallestStringWithSwaps(s, pairs) == "abc"

See also:

https://leetcode.com/problems/smallest-string-with-swaps